CS1.406 Advanced Algorithms (Spring 2022)

---

Announcements

• Teaching assistants: Dixit Kumar Garg and S Shodasakshari Vidya
• Schedule: Monday and Thursday, 11:30 – 12:55
• Classroom: SH-2 (2nd floor, C-1 Vindhya)

Lectures

1. Introduction to Randomized algorithms, RandQS (Includes the list of tentative topics)

   • References: Chapter 1 of [1], Chapter 1 & Section 2.4 of [2]

2. Min-Cut, and Las Vegas & Monte carlo

   • References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].

3. Coupon collector’s problem, Markov Inequality, Chebyshev’s inequality

   • References: Section 3.6 of [1] and Chapter 3 of [2].

4. Balls and Bins, Tail inequalities (contd.)

   • References: Chapter 3 of [1].

5. Concentration bounds, Chernoff bound, Error reduction, Set balancing

   • References: Chapter 4 of [2].

6. Martingales, Azuma’s inequality, Bounded difference inequalities.

   • References: [Kamath, Motwani, Palem and Spirakis ‘94], Section 4.3 of [1], and Chapter 12 of [2].

7. Martingales (contd.), Balls and Bins, Chromatic number of a random graph

   • References: Section 4.3 of [1], [Shamir and Spencer ‘87], Upfal’s slides, Sinclair’s lecture notes, and Chapter 12 of [2].

8. Randomized routing

   • References: Section 4.2 of [1], Section 4.5.1 of [2], Lovett’s course notes from UCSD, and J R Lee’s course notes from UWash.

9. Randomized routing (contd.), Maximum Satisfiability

   • References: Section 5.2 of [1], and Section 6.2.2 of [2].

10. MAXCUT, Derandomization with conditional probabilities

    • References: Section 6.2 and 6.3 of [2].

11. Introduction to Polynomial Identity Testing, Univariate Interpolation, Verifying Matrix Multiplication

    • References: Section 7.2 & 7.3 of [1], and Section 1.1 & 1.3 of [2].

12. DeMillo-Lipton-Schwartz–Zippel lemma, The isolation lemma and Mulmuley, Vazirani, and Vazirani algorithm for matching

    • References: Section 12.4 of [1], Section Moshkovitz’s alternate proof of DLSZ lemma, and Mulmuley-Vazirani-Vazirani ‘87

13. MVV (contd.), Maximal Independent Set

    • References: Section 12.3 of [1].

14. Maximal Independent Set (contd.)

    • References: Section 12.3 of [1].

15. Hashing: Universal Hashing, Perfect Hashing

    • References: Section 8.4 of [1], and Section 13.3 of [2].

16. Hashing: Universal Hashing, Perfect Hashing (contd.)

    • References: Section 8.4 of [1], and Section 13.3 of [2].

17. Approximate counting: DNFs

    • References: Section 11.2 of [1] and Sections 10.1 and 10.2 of [2].

18. Random walks and Markov chains

    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

19. Markov Chains – 2SAT

    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

20. Markov Chains – 3SAT

    • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

21. Karatsuba’s integer multiplication, Discrete Fourier Transform, Fast Fourier Transform.

    • References: Sections 1.1 – 1.3 and 2.2 of [6].

22. DFT in Mod-m rings, Chinese Remaindering Theorem, Schonhage-Strassen integer multiplication.

    • References: Sections 2.3 and 2.7 of [6].

23. Fermat’s little theorem, Fermat’s test, Miller-Rabin primality test, RSA encryption and Fingerprinting.

    • References: Section 14.6, and sections 7.4 – 7.6 of [1].

References

1. R. Motwani and P. Raghavan (1995), Randomized Algorithms, Cambridge University Press.
2. M. Mitzenmacher and E. Upfal (2005), Probability and Computing, Cambridge University Press.
3. N. Alon and J. Spencer (2015), The Probabilistic Method, Wiley, USA.
4. V. Shoup (2005), A Computational Introduction to Number Theory and Algebra, Cambridge University Press.
5. J. von zur Gathen and J. Gerhard (2003), Modern Computer Algebra, Cambridge University Press.
6. R. Brent and P. Zimmerman (2010), Modern Computer Arithmetic, Web draft.

Similar courses

See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).